package demo.DataStrucAndAlgo.recursion;

/**
 * @Auther: hjy(lc))
 * @Date: 2022/7/23-07-23-15:08
 * @Description：demo.DataStrucAndAlgo   递归解决迷宫问题
 * 事先约定：地图map 8行7列，0=未走过，1=墙壁，2=已走过，3=死路。
 * map[1][1]为起始点，map[6][5]为终止点
 * 在findWay方法中，利用递归找路。递归结束的条件是map[6][5]==2
 * 制定找路策略为：下-左-上-右。当还不是终止点就按照策略递归，
 * 经过策略找路也没找到新路，就把这个点标记为死路返回假。
 * 直到，遇到map[6][5]==2，说明找到路，否则没找到。
 */
public class Recursion_Maze {
    static String s = "";
    public static void main(String[] args) {
        //创造地图
        //约定：0 未走过， 1 墙壁， 2 已走过，3 死路
        int map[][] = new int[8][7];
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 7; j++) {
                if(i == 0 || i == 7){
                    map[i][j] = 1;
                }
                if(j ==  0 || j == 6){
                    map[i][j] = 1;
                }
            }
        }
        map[2][1] = map[2][2] = map[0][4] = map[1][4] = 1;
        //打印初始地图
        System.out.println("初始化地图： ");
        for (int[] item : map) {
            for (int temp : item) {
                System.out.print(temp + " ");
            }
            System.out.println();
        }
        //找路
        findWay(map,1,1);
        //打印找完路的地图
        System.out.println("找路结果：");
        for (int[] item : map) {
            for (int temp : item) {
                System.out.print(temp + " ");
            }
            System.out.println();
        }
        System.out.println(s);
    }

    /**
     * 找路方法
     * 找路策略：下-左-上-右
     * @param map
     * @param i
     * @param j
     */
    public static boolean findWay(int[][] map, int i, int j) {
        if(map[6][5] == 2){   //到了终点，找到路了
            return true;
        }else {
            if (map[i][j] == 0) {//到了新路
                map[i][j] = 2;
                if (findWay(map, i + 1, j)) {//向下走
                    s  = s + "D";
                    return true;
                } else if (findWay(map, i, j + 1)) {//向右走
                    s = s + "R";
                    return true;
                } else if (findWay(map, i - 1, j)) {//向上走
                    s = s + "U";
                    return true;
                } else if (findWay(map, i, j - 1)) {//向左走
                    s = s + "L";
                    return true;
                } else {
                    //此路不通，是死路
                    map[i][j] = 3;
                    return false;
                }
            } else {//没找到新路，有可能是1,2,3
                return false;
            }
        }
    }
}
